package main.function;

import main.string.utill.JsonUtil;
import org.junit.Test;

import java.util.*;

/**
 * 排序的各种方法 Created by ChengGM on 2017/5/9.
 */
public class BubblingSort {
	private List<Integer> getArr() {
		Set<Integer> set = new HashSet<Integer>();
		// 刚开始时集合长度为0，所在集合在为的时候就开始添加数据
		while (set.size() < 10) {
			set.add(new Random().nextInt(100));
		}
		List<Integer> arr = new ArrayList<>(set);
		System.out.println(JsonUtil.toJson(arr));
		return arr;
	}

	// 全用集合方法
	@Test
	public void test() throws Exception {

		List<Integer> list = new ArrayList<>();
		for (int i = 0; i < 100; i++) {
			Random random = new Random();
			list.add((Integer) random.nextInt(100));
		}
		Set<Integer> result = new HashSet<>(list);
		List<Integer> list2 = new ArrayList<>(result);
		System.out.println(JsonUtil.toJson(list));
		System.out.println(JsonUtil.toJson(list2));
		Collections.sort(list2);
		System.out.println(JsonUtil.toJson(list2));
	}

	// 使用冒泡
	@Test
	public void test3() throws Exception {
		int[] arr = new int[10];
		List<Integer> list = getArr();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = list.get(i);
		}
		System.out.println(JsonUtil.toJson(arr));

		// 冒泡排序
		for (int j = 0; j < arr.length; j++) {
			for (int k = 0; k < arr.length - j - 1; k++) {
				if (arr[k] > arr[k + 1]) {
					int temp = arr[k];
					arr[k] = arr[k + 1];
					arr[k + 1] = temp;
				}
			}
		}
		System.out.println(JsonUtil.toJson(arr));
	}

	// 快速排序
	@Test
	public void test4() throws Exception {
		Integer[] arr = new Integer[10];
		List<Integer> list = getArr();
		for (int i = 0; i < arr.length; i++) {
			arr[i] = list.get(i);
		}
		System.out.println(JsonUtil.toJson(arr));
		// 快速排序
		quickSort(arr, 0, arr.length - 1);
		System.out.println(JsonUtil.toJson(arr));

	}
    //快速排序核心算法
	public void quickSort(Integer[] data, int left, int right) {
		Integer middle, tempData;
		int i = left;
		int j = right;
		middle = data[(i + j) / 2];
		do {
		    //x<y 结果为-1，x>y结果为1，x=y结果为0
			while (data[i].compareTo(middle) < 0 && i < right)
				i++;
			while ((data[j].compareTo(middle) > 0 && j > left))
				j--;
			if (i <= j) {
				tempData = data[i];
				data[i] = data[j];
				data[j] = tempData;
				i++;
				j--;
			}
		} while (i <= j);
		if (i < right) {
			quickSort(data, i, right);
		}
		if (j > left) {
			quickSort(data, left, j);
		}
	}
}
